﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.SortCode
{
    class MergeSort
    {
        //====================================归并排序
        //归并排序是建立在归并操作上的一种有效排序算法。
        //和选择排序一样，归并排序的性能不受输入数据的影响，但比选择排序好，因为始终都是 O(nlogn) 的时间复杂度。
        //代价是需要额外的内存空间。
        //步骤：
        //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
        //设定两个指针，最初位置分别为两个已经排序序列的起始位置；
        //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
        //重复步骤 3 直到某一指针达到序列尾；
        //将另一序列剩下的所有元素直接复制到合并序列尾。

        public int[] Sort(int[] arr)
        {
            int len = arr.Length;
            if (len < 2)
                return arr;


            int middle = (int)Math.Floor((double)len / 2);
            int[] left = new int[middle];
            Array.Copy(arr, left, middle);
            int[] right = new int[len - middle];
            Array.Copy(arr, right, len - middle);

            return Merge(left, right);

        }
        int[] Merge(int[] left, int[] right)
        {
            int[] result = new int[left.Length + right.Length];
            int i = 0;
            while(left.Length > 0 && right.Length > 0)
            {
                if(left[0] <= right[0])
                {
                    result[i++] = left[0];
                    Array.Copy(left, left, left.Length);
                    
                }
            }
            return new int[2];
        }
    }
}
